class Solution:
    WORD_END = "end"
    def findWords(self, board, words):
        if not board or not board[0] or not words:
            return []

        # generate trie tree
        trie = {}
        for word in words:
            node = trie
            for char in word:
                node = node.setdefault(char, {})
            node[self.WORD_END] = word

        result, rows, cols = [], len(board), len(board[0])

        def _dfs(i, j, trie):
            c = board[i][j]
            if c not in trie: return
            trie = trie[c]

            if self.WORD_END in trie and trie[self.WORD_END]:
                result.append(trie[self.WORD_END])
                trie[self.WORD_END] = False

            board[i][j] = '#'

            for x, y in ((-1, 0), (1, 0), (0, -1), (0, 1)):
                new_x, new_y = x+i, y+j
                if 0<= new_x < rows and 0<= new_y < cols and board[new_x][new_y] != '#':
                     _dfs(new_x, new_y, trie)

            board[i][j] = c

        for i in range(rows):
            for j in range(cols):
                _dfs(i, j, trie)
        
        return result 




if __name__ == '__main__':
    board = [["o","a","a","n"],["e","t","a","e"],["i","h","k","r"],["i","f","l","v"]]
    words = ["oath","pea","eat","rain"]
    print(Solution().findWords(board, words))